/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode() {}
 * TreeNode(int val) { this.val = val; }
 * TreeNode(int val, TreeNode left, TreeNode right) {
 * this.val = val;
 * this.left = left;
 * this.right = right;
 * }
 * }
 */
class Solution {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(5);
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node6 = new TreeNode(6);
        TreeNode node7 = new TreeNode(7);
        TreeNode node8 = new TreeNode(8);
        TreeNode node9 = new TreeNode(9);
        root.left = node3;
        node3.left = node2;
        node3.right = node4;
        node2.left = node1;
        root.right = node6;
        node6.right = node8;
        node8.left = node7;
        node8.right = node9;
        TreeNode node = increasingBST(root);
        System.out.println(node.val);
    }

    private static TreeNode tail;

    public static TreeNode increasingBST(TreeNode root) {
        tail = null;
        return loop(root);
    }

    public static TreeNode loop(TreeNode root) {
        // 判断有没有左节点
        TreeNode head;
        if (null != root.left) {
            head = increasingBST(root.left);
            head.left = null;
            tail.right = root;
        } else {
            head = root;
        }
        // 判断有没有右节点
        if (null != root.right) {
            root.right = increasingBST(root.right);
        } else {
            tail = root;
        }
        root.left = null;
        tail.left = null;
        return head;
    }
}


class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}